//#define DEBUG

#include <iostream>
#include <fstream>
#include <cmath>
#include <queue>
#include <list>
#include <set>
using namespace std;

#define INFILE "nPuzzle.in3"
#define OUTFILE "nPuzzle.out"
#define STEP_COST 1
#define INF 300

#define LUCKY_NUMBER 541235797

#define MAX_N 4
#define MAX_DIRECTION 4
#define ZERO_TOWN 0
#define abs(a) (((a)>0)?(a):(-(a)))

const int dx[MAX_DIRECTION] = {1,0,-1,0};
const int dy[MAX_DIRECTION] = {0,1,0,-1};

/**
    Global variables
*/
int result;
int numberOfState;
int n,hcase;

/**
    Class State
    Define a state
*/
class State {
public:
    short int town[MAX_N][MAX_N];
    int g,h;

    State ();

    int f() const;
    bool operator < (const State &other) const;
    bool operator <= (const State &other) const;
    bool operator > (const State &other) const;
    bool operator >= (const State &other) const;
    bool operator == (const State &other) const;
};

/// Implements set for storing close nodes
int hash(const State &state);
set<State> closeNodes;

/// Implements priority queue for storing open nodes
class moref{
public:
  moref(){};
  bool operator() (const State& lhs, const State&rhs) const
  {
     if (lhs.f() == rhs.f()){
         return (lhs.g < rhs.g);
     } else {
        return (lhs.f() > rhs.f());
     }
  }
};
priority_queue<State,vector<State>,moref> openNodes;

State initState;    // the init state
State goalState;    // the goal state
int igoalState [MAX_N*MAX_N][2];

/**
    Read in data from the input file
*/
void readData();

/**
    Print out result to the output file
*/
void printOut();

/// Heuristic Functions
int h1(State &nextState);
int h2(State &nextState);
int h3(State &nextState);

/**
    Find the goal state using the heuristic function h
*/
void searching(int (*h)(State&));

/**
    Check if the problem is solvable or not
*/
bool solvable(State &state);

/** --------------------------------------------------------
    Main function
*/
int main(int argc, char **argv){
    readData();
    //if (solvable(initState)){
    switch (hcase){
        case 1: searching(h1); break;
        case 2: searching(h2); break;
        case 3: searching(h3); break;
    }
    //}
    printOut();
    return 0;
}
///----------------------------------------------------------
State::State(){
    g = 0;
    h = 0;
}

int State::f() const{
    return g+h;
}

bool State::operator < (const State &other) const {
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        if (this->town[i][j] > other.town[i][j])
            return false;
        else if (this->town[i][j] < other.town[i][j])
            return true;
    }

    return false;
}

bool State::operator > (const State &other) const {
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        if (this->town[i][j] > other.town[i][j])
            return true;
        else if (this->town[i][j] < other.town[i][j])
            return false;
    }

    return false;
}

bool State::operator <= (const State &other) const {
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        if (this->town[i][j] > other.town[i][j])
            return false;
        else if (this->town[i][j] < other.town[i][j])
            return true;
    }

    return true;
}

bool State::operator >= (const State &other) const {
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        if (this->town[i][j] > other.town[i][j])
            return true;
        else if (this->town[i][j] < other.town[i][j])
            return false;
    }

    return true;
}

bool State::operator == (const State &other) const {
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
        if (this->town[i][j] != other.town[i][j])
            return false;

    return true;
}

void readData(){
    ifstream fin (INFILE);

    // validate input file
    if (fin.fail()){
        cout << "Error input file!" << endl;
        return;
    }

    // read in n,k
    fin >> n >> hcase;

    n = ceil(sqrt(n));

    // Read in init state
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        fin >> initState.town[i][j];
    }

    // Read in goal state
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        fin >> goalState.town[i][j];
        igoalState[goalState.town[i][j]][0] = i;
        igoalState[goalState.town[i][j]][1] = j;
    }

    fin.close();
}

void printOut(){
    ofstream fo (OUTFILE);
    fo << result << " " << numberOfState;
    fo.close();
}


// Find a town in the puzzle
void findNumber(const State &state, int number, int &x, int &y){
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
        if (state.town[i][j] == number){
            x = i;
            y = j;
            return;
        }
    }
}

/**
    A* implementation
*/
bool inBound(int x, int y){
    if (x<0 || y <0) return false;
    if (x >= n || y>= n) return false;
    return true;
}
void searching(int (*h)(State&)){

    State nowState,nextState;
    int zx,zy;

    // initialize variables
    numberOfState = 0;
    openNodes.push(initState);
    closeNodes.insert(initState);
    closeNodes.clear();

    while (!openNodes.empty()){

        nowState = openNodes.top();
        openNodes.pop();
        //set<State>::iterator ii = closeNodes.find(nowState);
        //if (ii != closeNodes.end()) continue;
        if (closeNodes.insert(nowState).second == false) continue;  // insert nowSatte to closed nodes and check if the nowState is already considered
        //closeNodes.insert(nowState);

        #ifdef DEBUG
        cout << nowState.f()<<"|" <<nowState.g<<"|"<<nowState.h<< "|" << numberOfState  <<endl;
        #endif

        // check if the goal state is reached or not
        if (nowState == goalState){
            result = nowState.g;
            return;
        }

        // find the position of The ZERO TOWN
        findNumber(nowState,ZERO_TOWN,zx,zy);

        // try to move the zero town
        for (int i=0;i<MAX_DIRECTION;i++)
            if (inBound(zx+dx[i],zy+dy[i])){

                nextState = nowState;
                nextState.town[zx][zy] = nextState.town[zx+dx[i]][zy+dy[i]];
                nextState.town[zx+dx[i]][zy+dy[i]] = 0;

                set<State>::iterator ii = closeNodes.find(nextState);
                if (ii == closeNodes.end()){    // if the next state hasn't visited
                    // increase number of state
                    // calculate the heuristic function in the next state
                    nextState.h = (*h)(nextState);
                    #ifdef DEBUG
                    if (nextState.h < nowState.h-STEP_COST) nextState.h = nowState.h - STEP_COST;
                    #endif
                    nextState.g = nowState.g + STEP_COST;

                    // enqueue the next state
                    numberOfState ++;
                    openNodes.push(nextState);
                }

            }

    }

    result = -1;
}


/**
    Heuristic functions implementation
*/
bool solvable(State &state){
    bool visited[MAX_N][MAX_N];
    int count = 0;
    bool zero;
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
        visited[i][j] = false;

    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
    if ( !visited[i][j]){
        int x=i,y=j;
        zero = false;
        do {
            visited[x][y] = true;
            if (state.town[x][y] == 0) zero = true;
            findNumber(goalState,state.town[x][y],x,y);
        } while (x!=i || y!=j);
        if (!zero) count ++;
    }

    result = -1;
    numberOfState = 0;

    //return (count % 2 == n % 2);
    return true;
}

int h1(State &nextState){
    int result = 0;
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
    if (nextState.town[i][j] != 0 && (nextState.town[i][j] != goalState.town[i][j])){
        result ++;
    }

    return result;
}

int h2(State &nextState){
    int result = 0;
    int x,y;
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
    if (nextState.town[i][j] != 0){
        findNumber(goalState,nextState.town[i][j],x,y);
        result += abs(x-i)+abs(y-j);
    }

    return result;
}

// mahatan distances and linear conflict
int h3(State &nextState){
    int result = 0;

    // count mahattan distance
    int x,y,zx,zy,mindistance = INF;

    findNumber(nextState,0,zx,zy);
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
    if (nextState.town[i][j] != 0){
        findNumber(goalState,nextState.town[i][j],x,y);
        result += abs(x-i)+abs(y-j);
        if (( i != x || j!=y) && ((abs(zx-i)+abs(zy-j)) < mindistance)){
            mindistance = (abs(zx-i)+abs(zy-j));
        }
    }

    // the distance from ZERO_TOWN to the nearest missplaced town
    if (mindistance < INF && mindistance > 0) {
        result += 2*(mindistance - 1);
        //cout << "hehe" << endl;
    }

    // count the number of linear conflict pairs
    int numberOfPairs = 0;
    int first,second;
    bool rowList[MAX_N*MAX_N] = {false};
    bool colList[MAX_N*MAX_N] = {false};
    rowList[0] = true;
    colList[0] = true;

    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            first = nextState.town[i][j];
            // conflicts in rows
            if ((!rowList[first]) && (i == igoalState[first][0])){ // in the same row
                for (int k=j+1;k<n;k++){
                    second = nextState.town[i][k];
                    if ((!rowList[second]) && (i == igoalState[second][0])) // the second number in the same row
                    if (igoalState[first][1] > igoalState[second][1]){
                        numberOfPairs ++;   // in crease the number of conflict pairs
                        rowList[first] = true;
                        rowList[second] = true;
                    }
                }
            }

            // conflicts in columns
            if ((!colList[first]) && (j == igoalState[first][1])){ // in the same column
                for (int k= i+1;k<n;k++){
                    second = nextState.town[k][j];      // the second number in the same column
                    if ((!colList[second]) && (j == igoalState[second][1])) // the same column
                    if (igoalState[first][0] > igoalState[second][0]){
                        numberOfPairs ++; // in crease the number of conflict pairs
                        colList[first] = true;
                        colList[second] = true;
                    }
                }
            }
        }
    }
    result += 2*numberOfPairs;

    return result;
}
